package william.stack;

import java.util.Stack;

/**
 * @author ZhangShenao
 * @date 2024/1/23
 * @description <a href="https://leetcode.cn/problems/min-stack-lcci/description/">...</a>
 */
public class 面试题_03_02_栈的最小值 {
    /**
     * 维护两个栈：数据栈和最小栈，两个栈同步操作。最小栈本质上维护的是，当每个元素压栈后，当前所有元素的最小值。
     * 当有元素压栈时，首先压入数据栈。然后将该元素与最小栈栈顶的元素进行比较：
     * - 如果该元素 < 最小栈栈顶元素，则将该元素压入最小栈。
     * - 否则将最小栈栈顶元素再次压栈。
     * 当有元素弹栈时，将数据栈和最小栈同时弹栈。
     */
    class MinStack {
        /**
         * 数据栈
         */
        private Stack<Integer> values;

        /**
         * 最小栈
         */
        private Stack<Integer> min;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            //初始化数据栈和最小栈
            this.values = new Stack<>();
            this.min = new Stack<>();
        }

        public void push(int x) {
            //首先将元素压入数据栈
            values.push(x);

            //将元素与最小栈栈顶元素进行比较
            if (min.isEmpty() || x < min.peek()) {   //如果该元素 < 最小栈栈顶元素，则将该元素压入最小栈。
                min.push(x);
            } else {    //否则将最小栈栈顶元素再次压栈。
                min.push(min.peek());
            }
        }

        public void pop() {
            //将数据栈和最小栈同时弹栈
            values.pop();
            min.pop();
        }

        public int top() {
            //返回数据栈栈顶元素
            return values.peek();
        }

        public int getMin() {
            //返回最小栈栈顶元素
            return min.peek();
        }
    }
}
